home *** CD-ROM | disk | FTP | other *** search
- Path: garden.csc.calpoly.edu!not-for-mail
- From: dstubbs@garden.csc.calpoly.edu (Dan Stubbs)
- Newsgroups: comp.lang.c
- Subject: Re: Sorting algorithm - In search of
- Date: 3 Mar 1996 14:06:31 -0800
- Organization: Cal Poly, San Luis Obispo
- Message-ID: <4hd557$ai2@garden.csc.calpoly.edu>
- References: <4h4jmq$3bh@news.cis.nctu.edu.tw> <4h6glr$ab6@utrhcs.cs.utwente.nl> <4hat5g$bdq@fohnix.metronet.com>
- NNTP-Posting-User: dstubbs@garden.csc.calpoly.edu
-
- In article <4hat5g$bdq@fohnix.metronet.com>,
- Stan Milam <milam@fohnix.metronet.com> wrote:
- >Frans F.J. Faase (faase@cs.utwente.nl) wrote:
- >: In article <4h4jmq$3bh@news.cis.nctu.edu.tw>, Don Pierce <don@pierce.geometrics.com> writes:
- >: |> I am looking for an efficient sorting alogorithm
- >: |> to sort an array of floats. I prefer a non-recursive
- >: |> type because I heard they were inefficient on large data
- >: |> sets. My array contains upt 10000 elements
- >
- >What in the world is wrong with the standard qsort() function. My experience
- >with it is that it is very fast. Moreover, it is not restricted to a single
- >data type.
- >
- The comment about avoiding recursive sort implementations is not one
- that I follow. A common way to implement quicksort is to apply recursion
- to long subintervals and to apply non-recursive insertion sort to short
- (nearly sorted) subintervals. Such a combination is hard to beat. You should
- seek some solid evidence before avoiding a good implementation of (recursive)
- quicksort.
-
- I agree with the comment about qsort. I many cases it is the sort technique
- of choice. However, there may be cases in which qsort is not the best. The
- question here concerns sorting an array of floats. It is probably possible
- to implement quicksort specifically for an array of floats so that it is
- faster than the (generic) qsort. If sorting the array of floats is frequent
- and time consuming it is no doubt worth comparing qsort with good
- implementations that are hard wired for the specific problem at hand.
-
- Further, some implementations of qsort do not perform well for certain
- initial distributions of the data to sort. If you have such a case, then
- you need to replace qsort with another implementation of quicksort that
- is efficient for your initial distribution.
-
- For the occasional sort application, by all means, use qsort. For production
- sort problems test qsort to make sure it provides the performance you need.
- If it doesn't investigate an implementation of quicksort that is customized
- to your sorting problem.
-
-
-
-